Search Results

Documents authored by C. S., Karthik

Document
DOI: 10.4230/DagRep.13.7.96
Parameterized Approximation: Algorithms and Hardness (Dagstuhl Seminar 23291)

Authors: Karthik C. S., Parinya Chalermsook, Joachim Spoerhase, Meirav Zehavi, and Martin Herold

Published in: Dagstuhl Reports, Volume 13, Issue 7 (2024)

Abstract
Parameterization and approximation are two established approaches of coping with intractability in combinatorial optimization. In this Dagstuhl Seminar, we studied parameterized approximation as a relatively new algorithmic paradigm that combines these two popular research areas. In particular, we analyzed the solution quality (approximation ratio) as well as the running time of an algorithm in terms of a parameter that captures the "complexity" of a problem instance. While the field has grown and yielded some promising results, our understanding of the area is rather ad-hoc compared to our knowledge in approximation or parameterized algorithms alone. In this seminar, we brought together researchers from both communities in order to bridge this gap by accommodating the exchange and unification of scientific knowledge.
Cite as

Karthik C. S., Parinya Chalermsook, Joachim Spoerhase, Meirav Zehavi, and Martin Herold. Parameterized Approximation: Algorithms and Hardness (Dagstuhl Seminar 23291). In Dagstuhl Reports, Volume 13, Issue 7, pp. 96-107, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{c.s._et_al:DagRep.13.7.96,
  author =	{C. S., Karthik and Chalermsook, Parinya and Spoerhase, Joachim and Zehavi, Meirav and Herold, Martin},
  title =	{{Parameterized Approximation: Algorithms and Hardness (Dagstuhl Seminar 23291)}},
  pages =	{96--107},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{13},
  number =	{7},
  editor =	{C. S., Karthik and Chalermsook, Parinya and Spoerhase, Joachim and Zehavi, Meirav and Herold, Martin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.7.96},
  URN =		{urn:nbn:de:0030-drops-197764},
  doi =		{10.4230/DagRep.13.7.96},
  annote =	{Keywords: approximation algorithms, Hardness of approximation, Parameterized algorithms}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.17
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic

Authors: Karthik C. S. and Pasin Manurangsi

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
Given a set of n points in R^d, the (monochromatic) Closest Pair problem asks to find a pair of distinct points in the set that are closest in the l_p-metric. Closest Pair is a fundamental problem in Computational Geometry and understanding its fine-grained complexity in the Euclidean metric when d=omega(log n) was raised as an open question in recent works (Abboud-Rubinstein-Williams [FOCS'17], Williams [SODA'18], David-Karthik-Laekhanukit [SoCG'18]). In this paper, we show that for every p in R_{>= 1} cup {0}, under the Strong Exponential Time Hypothesis (SETH), for every epsilon>0, the following holds: - No algorithm running in time O(n^{2-epsilon}) can solve the Closest Pair problem in d=(log n)^{Omega_{epsilon}(1)} dimensions in the l_p-metric. - There exists delta = delta(epsilon)>0 and c = c(epsilon)>= 1 such that no algorithm running in time O(n^{1.5-epsilon}) can approximate Closest Pair problem to a factor of (1+delta) in d >= c log n dimensions in the l_p-metric. In particular, our first result is shown by establishing the computational equivalence of the bichromatic Closest Pair problem and the (monochromatic) Closest Pair problem (up to n^{epsilon} factor in the running time) for d=(log n)^{Omega_epsilon(1)} dimensions. Additionally, under SETH, we rule out nearly-polynomial factor approximation algorithms running in subquadratic time for the (monochromatic) Maximum Inner Product problem where we are given a set of n points in n^{o(1)}-dimensional Euclidean space and are required to find a pair of distinct points in the set that maximize the inner product. At the heart of all our proofs is the construction of a dense bipartite graph with low contact dimension, i.e., we construct a balanced bipartite graph on n vertices with n^{2-epsilon} edges whose vertices can be realized as points in a (log n)^{Omega_epsilon(1)}-dimensional Euclidean space such that every pair of vertices which have an edge in the graph are at distance exactly 1 and every other pair of vertices are at distance greater than 1. This graph construction is inspired by the construction of locally dense codes introduced by Dumer-Miccancio-Sudan [IEEE Trans. Inf. Theory'03].
Cite as

Karthik C. S. and Pasin Manurangsi. On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{c.s._et_al:LIPIcs.ITCS.2019.17,
  author =	{C. S., Karthik and Manurangsi, Pasin},
  title =	{{On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{17:1--17:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.17},
  URN =		{urn:nbn:de:0030-drops-101100},
  doi =		{10.4230/LIPIcs.ITCS.2019.17},
  annote =	{Keywords: Closest Pair, Bichromatic Closest Pair, Contact Dimension, Fine-Grained Complexity}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.11
Towards a General Direct Product Testing Theorem

Authors: Elazar Goldenberg and Karthik C. S.

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract
The Direct Product encoding of a string a in {0,1}^n on an underlying domain V subseteq ([n] choose k), is a function DP_V(a) which gets as input a set S in V and outputs a restricted to S. In the Direct Product Testing Problem, we are given a function F:V -> {0,1}^k, and our goal is to test whether F is close to a direct product encoding, i.e., whether there exists some a in {0,1}^n such that on most sets S, we have F(S)=DP_V(a)(S). A natural test is as follows: select a pair (S,S')in V according to some underlying distribution over V x V, query F on this pair, and check for consistency on their intersection. Note that the above distribution may be viewed as a weighted graph over the vertex set V and is referred to as a test graph. The testability of direct products was studied over various domains and test graphs: Dinur and Steurer (CCC '14) analyzed it when V equals the k-th slice of the Boolean hypercube and the test graph is a member of the Johnson graph family. Dinur and Kaufman (FOCS '17) analyzed it for the case where V is the set of faces of a Ramanujan complex, where in this case V=O_k(n). In this paper, we study the testability of direct products in a general setting, addressing the question: what properties of the domain and the test graph allow one to prove a direct product testing theorem? Towards this goal we introduce the notion of coordinate expansion of a test graph. Roughly speaking a test graph is a coordinate expander if it has global and local expansion, and has certain nice intersection properties on sampling. We show that whenever the test graph has coordinate expansion then it admits a direct product testing theorem. Additionally, for every k and n we provide a direct product domain V subseteq (n choose k) of size n, called the Sliding Window domain for which we prove direct product testability.
Cite as

Elazar Goldenberg and Karthik C. S.. Towards a General Direct Product Testing Theorem. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{goldenberg_et_al:LIPIcs.FSTTCS.2018.11,
  author =	{Goldenberg, Elazar and C. S., Karthik},
  title =	{{Towards a General Direct Product Testing Theorem}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.11},
  URN =		{urn:nbn:de:0030-drops-99105},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.11},
  annote =	{Keywords: Property Testing, Direct Product, PCP, Johnson graph, Ramanujan Complex, Derandomization}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.12
Communication Complexity of Correlated Equilibrium with Small Support

Authors: Anat Ganor and Karthik C. S.

Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)

Abstract
We define a two-player N x N game called the 2-cycle game, that has a unique pure Nash equilibrium which is also the only correlated equilibrium of the game. In this game, every 1/poly(N)-approximate correlated equilibrium is concentrated on the pure Nash equilibrium. We show that the randomized communication complexity of finding any 1/poly(N)-approximate correlated equilibrium of the game is Omega(N). For small approximation values, our lower bound answers an open question of Babichenko and Rubinstein (STOC 2017).
Cite as

Anat Ganor and Karthik C. S.. Communication Complexity of Correlated Equilibrium with Small Support. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ganor_et_al:LIPIcs.APPROX-RANDOM.2018.12,
  author =	{Ganor, Anat and C. S., Karthik},
  title =	{{Communication Complexity of Correlated Equilibrium with Small Support}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.12},
  URN =		{urn:nbn:de:0030-drops-94163},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.12},
  annote =	{Keywords: Correlated equilibrium, Nash equilibrium, Communication complexity}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.17
Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH

Authors: Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., and Pasin Manurangsi

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
The k-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over F_2, which can be stated as follows: given a generator matrix A and an integer k, determine whether the code generated by A has distance at most k. Here, k is the parameter of the problem. The question of whether k-Even Set is fixed parameter tractable (FPT) has been repeatedly raised in literature and has earned its place in Downey and Fellows' book (2013) as one of the "most infamous" open problems in the field of Parameterized Complexity. In this work, we show that k-Even Set does not admit FPT algorithms under the (randomized) Gap Exponential Time Hypothesis (Gap-ETH) [Dinur'16, Manurangsi-Raghavendra'16]. In fact, our result rules out not only exact FPT algorithms, but also any constant factor FPT approximation algorithms for the problem. Furthermore, our result holds even under the following weaker assumption, which is also known as the Parameterized Inapproximability Hypothesis (PIH) [Lokshtanov et al.'17]: no (randomized) FPT algorithm can distinguish a satisfiable 2CSP instance from one which is only 0.99-satisfiable (where the parameter is the number of variables). We also consider the parameterized k-Shortest Vector Problem (SVP), in which we are given a lattice whose basis vectors are integral and an integer k, and the goal is to determine whether the norm of the shortest vector (in the l_p norm for some fixed p) is at most k. Similar to k-Even Set, this problem is also a long-standing open problem in the field of Parameterized Complexity. We show that, for any p > 1, k-SVP is hard to approximate (in FPT time) to some constant factor, assuming PIH. Furthermore, for the case of p = 2, the inapproximability factor can be amplified to any constant.
Cite as

Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., and Pasin Manurangsi. Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bhattacharyya_et_al:LIPIcs.ICALP.2018.17,
  author =	{Bhattacharyya, Arnab and Ghoshal, Suprovat and C. S., Karthik and Manurangsi, Pasin},
  title =	{{Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.17},
  URN =		{urn:nbn:de:0030-drops-90214},
  doi =		{10.4230/LIPIcs.ICALP.2018.17},
  annote =	{Keywords: Parameterized Complexity, Inapproximability, Even Set, Minimum Distance Problem, Shortest Vector Problem, Gap-ETH}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.28
On the Complexity of Closest Pair via Polar-Pair of Point-Sets

Authors: Roee David, Karthik C. S., and Bundit Laekhanukit

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
Every graph G can be represented by a collection of equi-radii spheres in a d-dimensional metric Delta such that there is an edge uv in G if and only if the spheres corresponding to u and v intersect. The smallest integer d such that G can be represented by a collection of spheres (all of the same radius) in Delta is called the sphericity of G, and if the collection of spheres are non-overlapping, then the value d is called the contact-dimension of G. In this paper, we study the sphericity and contact dimension of the complete bipartite graph K_{n,n} in various L^p-metrics and consequently connect the complexity of the monochromatic closest pair and bichromatic closest pair problems.
Cite as

Roee David, Karthik C. S., and Bundit Laekhanukit. On the Complexity of Closest Pair via Polar-Pair of Point-Sets. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{david_et_al:LIPIcs.SoCG.2018.28,
  author =	{David, Roee and C. S., Karthik and Laekhanukit, Bundit},
  title =	{{On the Complexity of Closest Pair via Polar-Pair of Point-Sets}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{28:1--28:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.28},
  URN =		{urn:nbn:de:0030-drops-87412},
  doi =		{10.4230/LIPIcs.SoCG.2018.28},
  annote =	{Keywords: Contact dimension, Sphericity, Closest Pair, Fine-Grained Complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.24
Ham Sandwich is Equivalent to Borsuk-Ulam

Authors: Karthik C. S. and Arpan Saha

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
The Borsuk-Ulam theorem is a fundamental result in algebraic topology, with applications to various areas of Mathematics. A classical application of the Borsuk-Ulam theorem is the Ham Sandwich theorem: The volumes of any n compact sets in R^n can always be simultaneously bisected by an (n-1)-dimensional hyperplane. In this paper, we demonstrate the equivalence between the Borsuk-Ulam theorem and the Ham Sandwich theorem. The main technical result we show towards establishing the equivalence is the following: For every odd polynomial restricted to the hypersphere f:S^n->R, there exists a compact set A in R^{n+1}, such that for every x in S^n we have f(x)=vol(A cap H^+) - vol(A cap H^-), where H is the oriented hyperplane containing the origin with x as the normal. A noteworthy aspect of the proof of the above result is the use of hyperspherical harmonics. Finally, using the above result we prove that there exist constants n_0, epsilon_0>0 such that for every n>= n_0 and epsilon <= epsilon_0/sqrt{48n}, any query algorithm to find an epsilon-bisecting (n-1)-dimensional hyperplane of n compact set in [-n^4.51,n^4.51]^n, even with success probability 2^-Omega(n), requires 2^Omega(n) queries.
Cite as

Karthik C. S. and Arpan Saha. Ham Sandwich is Equivalent to Borsuk-Ulam. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{c.s._et_al:LIPIcs.SoCG.2017.24,
  author =	{C. S., Karthik and Saha, Arpan},
  title =	{{Ham Sandwich is Equivalent to Borsuk-Ulam}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{24:1--24:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.24},
  URN =		{urn:nbn:de:0030-drops-72325},
  doi =		{10.4230/LIPIcs.SoCG.2017.24},
  annote =	{Keywords: Ham Sandwich theorem, Borsuk-Ulam theorem, Query Complexity, Hyperspherical Harmonics}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact